#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution1 {
public:
	ListNode* reverseList(ListNode* head) {
		ListNode* tmp;
		ListNode* cur = head;
		ListNode* pre = NULL;
		while(cur){
			tmp = cur->next;
			cur->next = pre;
			pre = cur;
			cur = tmp;
		}
		return pre;
	}
};

class Solution2 {
public:
	ListNode* reverse(ListNode* pre,ListNode* cur){
		if(cur == NULL){
			return pre;
		}
		ListNode* tmp = cur->next;
		cur->next = pre;
		return reverse(cur,tmp);
	}
	ListNode* reverseList(ListNode* head) {
		return reverse(NULL,head);
	}
};
class Solution3 {
public:
	ListNode* reverseList(ListNode* head) {
		if(head == NULL){
			return NULL;
		}
		if(head->next == NULL){
			return head;
		}
		ListNode* last = reverseList(head->next);
		head->next->next = head;
		head->next = NULL;
		return last;
	}
};
int main(){
	
	return 0;
}
